package leetcode_acm.array;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月20日 19:25
 */
public class MinWindow {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        //1.定义需求窗口并且初始化
        int[] need = new int[128];
        int needSize = 0;
        for (char c : t) {
            if (need[c] == 0) {
                needSize++;
            }
            need[c]++;
        }
        //2.定义主窗口
        int[] windows = new int[128];
        int left = 0,right = 0,valid = 0;
        int[] min = new int[]{0,s.length+1};
        //3.开始滑动窗口
        while (right < s.length){
            int rightChar = s[right++];
            if(need[rightChar] != 0){
                windows[rightChar]++;
                if(need[rightChar] == windows[rightChar]){
                    valid++;
                }
            }
            while (needSize == valid){
                if(right - left <= min[1] - min[0]){
                    min[1] = right;
                    min[0] = left;
                }
                //此处更新答案
                int leftChar = s[left++];
                if(need[leftChar]!=0){
                    if(need[leftChar] == windows[leftChar]){
                        valid--;
                    }
                    windows[leftChar]--;
                }
            }
        }
        if(min[1] == s.length+1){
            return "";
        }
        return ss.substring(min[0],min[1]);
    }

    @Test
    public void test(){
        System.out.println(minWindow("ADOBECODEBANC","ABC"));
    }
}
